#include <stdio.h>
#include <stdlib.h>

/**
 * 顺序表实现循环队列
 */
typedef struct Queue{
    int * arr;
    // 队列的最大容量
    int capacity;
    // 队头，队尾
    int front, rear;
} * QueueArr;

/**
 * 初始化队列
 */
void initQueue(QueueArr queueArr){
    queueArr->arr = malloc(sizeof (int) * 10);
    queueArr->capacity = 10;
    // 牺牲一个存储单元
    queueArr->front = queueArr->rear = 0;
}

/**
 * 入队
 */
_Bool offerQueue(QueueArr queueArr, int data) {
    int currentRear = (queueArr->rear + 1) % queueArr->capacity;
    // 队列满
    if(currentRear == queueArr->front) {
        return 0;
    }
    queueArr->arr[currentRear] = data;
    queueArr->rear++;
    return 1;
}

/**
 * 出队
 */
int pollQueue(QueueArr queueArr) {
    // 队列空
    if(queueArr->front == queueArr->rear) {
        return INT_MAX;
    }
    queueArr->front = (queueArr->front + 1) % queueArr->capacity;
    return queueArr->arr[queueArr->front];
}

void printQueue(QueueArr queueArr){
    printf("<<< ");
    int i = queueArr->front;   //遍历队列需要从队首开始
    do {
        i = (i + 1) % queueArr->capacity;   //先向后循环移动
        printf("%d ", queueArr->arr[i]);  //然后打印当前位置上的元素
    } while (i != queueArr->rear);   //当到达队尾时，结束
    printf("<<<\n");
}

_Bool isEmpty(QueueArr queueArr) {
    return queueArr->front == queueArr->rear;
}




int main() {
    struct Queue queue;
    initQueue(&queue);
    for (int i = 0; i < 5; ++i) {
        offerQueue(&queue, i * 100);
    }
    printQueue(&queue);
    while (!isEmpty(&queue)) {
        printf("%d ", pollQueue(&queue));
    }
}



#include <stdio.h>
#include <stdlib.h>

/**
 * 链表实现循环队列
 */
// 节点
typedef struct Node{
    int data;
    struct Node * next;
} * LNode;

// 队列的头尾指针
typedef struct Queue {
    struct Node * front, * rear;
} * LQueue;

/**
 * 初始化队列
 */
void initQueue(LQueue queue, LNode lNode){
    // 头节点
    lNode = malloc(sizeof (LNode));
    // 队头和队尾指针都指向该头节点
    queue->front = queue->rear = lNode;
}

/**
 * 入队
 */
_Bool offerQueue(LQueue queue, int data) {
    LNode newNode = malloc(sizeof (LNode));
    if(newNode == NULL) {
        return 0;
    }
    newNode->data = data;
    newNode->next = NULL;
    queue->rear->next = newNode;
    queue->rear = newNode;
    return 1;
}

/**
 * 出队
 */
int pollQueue(LQueue queue) {
    // 队列空
    if(queue->front == queue->rear) {
        return INT_MAX;
    }
    LNode tempNode = queue->front->next;
    int data = tempNode->data;
    // 队列中只有一个元素，队尾需回到头节点
    if(tempNode->next == NULL) {
        queue->rear = queue->front;
    }
    queue->front->next = tempNode->next;
    free(tempNode);
    return data;
}

void printQueue(LQueue queue){
    printf("<<< ");
    LNode node = queue->front->next;
    while (node) {
        printf("%d ", node->data);
        if(node == queue->rear) break;    //当已经打印最后一个元素后，再结束
        else node = node->next;
    }
    printf("<<<\n");
}

_Bool isEmpty(LQueue lQueue) {
    return lQueue->front == lQueue->rear;
}




int main() {
    struct Queue queue;
    struct Node node;
    initQueue(&queue, &node);
    for (int i = 0; i < 5; ++i) {
        offerQueue(&queue, i * 100);
    }
    printQueue(&queue);
    while (!isEmpty(&queue)) {
        printf("%d ", pollQueue(&queue));
    }
}






